package org.wkg.lesson03;

import java.util.*;

public class Demo_300 {
    public static void main(String[] args) {
        System.out.println(lengthOfLongestSubstring("aabaab!bb"));
    }

    public static int lengthOfLongestSubstring(String s) {
        HashSet<Character> hashSet = new HashSet<>();
        int len = 0;
        for (int left = 0, right = 0; right < s.length(); right++) {

            char ch = s.charAt(right);
            while (hashSet.contains(ch)) {
                hashSet.remove(s.charAt(left++));
            }
            hashSet.add(ch);
            len = Math.max(len, right - left + 1);
        }
        return len;
    }

    public int lengthOfLongestSubstring1(String s) {
        HashSet<Character> hashSet = new HashSet<>();
        int len = 0;
        for (int left = 0, right = 0; right < s.length(); right++) {
            char ch = s.charAt(right);
            while (hashSet.contains(ch)) {
                hashSet.remove(s.charAt(left++));
            }
            hashSet.add(ch);
            len = Math.max(len, right - left + 1);
        }
        return len;
    }

    public int lengthOfLongestSubstring2(String s) {
        char[] ss = s.toCharArray();
        int[] array = new int[128];
        int left = 0, right = 0, len = s.length(), count = 0;
        while (right < len) {
            array[ss[right]]++;
            while (array[ss[right]] > 1) {
                array[ss[left++]]--;
            }
            count = Math.max(count, right - left + 1);
        }
        return count;
    }


    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> ret = new ArrayList<>();
        // 1. 排序
        Arrays.sort(nums);
        // 2. 利⽤双指针解决问题
        int n = nums.length;
        for (int i = 0; i < n; ) {// 固定数 a {
            if (nums[i] > 0) break; // ⼩优化
            int left = i + 1, right = n - 1, target = -nums[i];
            while (left < right) {
                int sum = nums[left] + nums[right];
                if (sum > target) right--;
                else if (sum < target) left++;
                else {
                    // nums[i] nums[left] num[right]
                    ret.add(new ArrayList<Integer>(Arrays.asList(nums[i], nums[left], nums[right])));
                    left++;
                    right--; // 缩⼩区间继续寻找
                    // 去重：left right
                    while (left < right && nums[left] == nums[left - 1]) left++;
                    while (left < right && nums[right] == nums[right + 1]) right--;
                }
            }
            // 去重：i
            i++;
            while (i < n && nums[i] == nums[i - 1]) i++;
        }
        return ret;
    }


    public List<List<Integer>> fourSum(int[] nums, int target) {
        List<List<Integer>> ret = new ArrayList<>();
        // 1. 排序
        Arrays.sort(nums);
        // 2. 利⽤双指针解决问题
        int n = nums.length;
        for (int i = 0; i < n; ) {// 固定数 a {
            // 三数之和
            for (int j = i + 1; j < n; ) {// 固定数 b
                // 双指针
                int left = j + 1, right = n - 1;
                long aim = (long) target - nums[i] - nums[j];
                while (left < right) {
                    int sum = nums[left] + nums[right];
                    if (sum > aim) right--;
                    else if (sum < aim) left++;
                    else {
                        ret.add(Arrays.asList(nums[i], nums[j], nums[left++], nums[right--]));
                        // 去重⼀
                        while (left < right && nums[left] == nums[left - 1]) left++;
                        while (left < right && nums[right] == nums[right + 1]) right--;
                    }
                }
                // 去重⼆
                j++;
                while (j < n && nums[j] == nums[j - 1]) j++;
            }
            // 去重三
            i++;
            while (i < n && nums[i] == nums[i - 1]) i++;
        }
        return ret;
    }


}
